package A一周刷爆LeetCode.A基础班.C认识NlogN的排序;

import A一周刷爆LeetCode.A基础班.B认识复杂度和简单排序算法.Sort;

/**
 * @author wei.zhao
 * @description: 归并排序
 * @date 2022年01月12日 11:31
 */
public class Code01_MergeSort extends Sort {

    @Override
    public void sort(int[] arr) {
        if (null == arr || arr.length < 2) {
            return;
        }
        mergeSort(arr, 0, arr.length - 1);
    }

    public void mergeSort(int[] arr, int l, int r) {
        if (l == r) {
            return;
        }
        int mid = l + ((r - l) >> 1);
        mergeSort(arr, l, mid);
        mergeSort(arr, mid + 1, r);
        merge(arr, l, mid, r);
    }

    private void merge(int[] arr, int l, int mid, int r) {
        int[] temp = new int[r - l + 1];
        int lp = l;
        int rp = mid + 1;
        //将范围内的数排序
        for (int i = 0; i < temp.length; i++) {
            if (lp > mid) {
                //左边的溢出
                temp[i] = arr[rp++];
            } else if (rp > r) {
                //右边的溢出
                temp[i] = arr[lp++];
            } else if (arr[lp] >= arr[rp]) {
                //左边的比较大
                temp[i] = arr[rp++];
            } else if (arr[lp] < arr[rp]) {
                //右边的比较大
                temp[i] = arr[lp++];
            }
        }
        //将排序后的数字放回原数组
        for (int i = 0; i < temp.length; i++) {
            arr[l + i] = temp[i];
        }
    }

}
